#include "Train.h"

class Solution {
public:
   int trap(vector<int>& height) {
       stack<int> s;
       int ans = 0;
       for (int i = 0; i < height.size(); i++) {
           while (!s.empty() && height[s.top()] < height[i])
           {
               int min_h = height[s.top()];//记录弹出柱子的高度
               s.pop();
               if (s.empty()) break;
               //计算出弹出柱子两侧相邻最矮柱子的高度与弹出柱子高度差，再乘以下标差，此时就为新增雨水面积
               ans = ans + (min(height[s.top()], height[i]) - min_h) * (i - s.top() - 1); 
           }
           s.push(i);
       }
       return ans;
   }
};